package com.jjlin.chapter_3;
import java.util.*;

public class CD163{
    //二叉树节点
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static TreeNode createBinaryTree(int[][] nums, int root){
        HashMap<Integer, TreeNode> map = new HashMap<>();
        int rows = nums.length;
        int cols = nums[0].length;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(nums[i][j] != 0 && !map.containsKey(nums[i][j]))
                    map.put(nums[i][j], new TreeNode(nums[i][j]));

        for(int i = 0; i < rows; i++){
            TreeNode node = map.get(nums[i][0]);
            if(nums[i][1] != 0){
                node.left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                node.right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //先序序列化
    public static String serialByPre(TreeNode root){
        if(root == null)
            return "";
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            sb.append(node == null ? "#!" : (node.val + "!"));
            if(node != null){
                stack.push(node.right);
                stack.push(node.left);
            }
        }
        return sb.toString();
    }

    //层序序列化
    public static String serialByLevel(TreeNode root){
        if(root == null)
            return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            sb.append(node == null ? "#!" : (node.val + "!"));
            if(node != null){
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        TreeNode head = createBinaryTree(nums, root);
        System.out.println(serialByPre(head));
        System.out.println(serialByLevel(head));
    }
}


